import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] arr){
        // 初始化一个临时数组，避免在排序的过程中频繁的生成数组
        int[] tmp = new int[arr.length];
        sort(arr,0,arr.length-1,tmp);
    }

    /**
     * 归并排序算法的实现 -- 使用递归
     * @param arr 需要排序的数组
     * @param left 左边开始的节点
     * @param right 右边开始的节点
     * @param tmp 临时数组
     */
    private static void sort(int[] arr, int left, int right, int[] tmp) {
        if(left < right){
            // 定义中间节点
            int mid = (left + right) / 2;

            // 对左边子序列进行归并排序
            sort(arr,left,mid,tmp);

            // 对右边子序列进行归并排序
            sort(arr,mid + 1,right,tmp);

            // 合并左右两个子序列
            merge(arr,left,mid,right,tmp);
        }
    }

    /**
     * 对左右子序列进行合并操作
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @param tmp
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] tmp) {

        // 左子序列指针的初始化
        int i = left;
        // 右子序列指针的初始化
        int j = mid + 1;
        // 临时数组指针的初始化
        int t = 0;

        // 比较左右子序列的值，将较小的值依次放入tmp临时数组中
        while (i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                tmp[t++] = arr[i++];
            }else {
                tmp[t++] = arr[j++];
            }
        }

        // 比较结束以后，会存在某一个子序列的值，还没有放进临时数组，因此需要将这些值放入临时数组

        // 将左子序列剩余元素放入数组
        while (i <= mid){
            tmp[t++] = arr[i++];
        }

        // 将右子序列剩余元素放入数组
        while (j <= right){
            tmp[t++] = arr[j++];
        }

        // 将临时数组的指针置为0
        t = 0;

        // 将临时数组中的数据复制到目标数组中
        while (left<=right){
            arr[left++] = tmp[t++];
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = {34,5,6,3,78};
        System.out.println(Arrays.toString(arr));
        mergeSort(arr);
    }
}